\documentclass[a4paper,10pt]{article}
\usepackage[margin=2.5cm, nohead]{geometry}
\usepackage{palatino, url, multicol}
\usepackage{graphicx}
%\usepackage{verbatim}

\title{Description of Datastructures project}
\author{Chiel Kooijman \& Maarten de Waard\\\small 5743028 5894883}

\begin{document}
\maketitle
\section{Game}
For the Data Structures AI  assignment we chose to do the game ``Scotland
Yard''.  Scotland yard is a game where several detectives try to find one bad
guy.  Persons are always on a node (e.g. bus stop or tube station). Nodes are
connected by transportation possibilities. There are four ways of
transportation: Taxi, Bus, Subway or Boat. To move from one node to another, a
person uses a transportation card for one way of transportation. The number of
cards a player has are limited.

There are two kinds of persons: The detectives and Mr. X. The goal of the game
for the detectives is to capture (i.e. visit the same node at the same time)
Mr. X. in 24 turns. The only thing the detectives know is what
kind of transportation Mr. X. uses, and at fixed time-points (namely turns 3,
8, 13, 18, and 24), Mr. X. has to reveal his location.

All participants start in random locations.

\section{Representation}
The board is represented by nodes (with a unique number) and connections to
other nodes. We have downloaded a list of nodes and their connections from an
open-source project, which we will use to generate a graph that represents the
map.

The task for the AI will be that of the detectives. It will consist of a
multi-agent that tries to find Mr. X., like ordinary people playing the game
would do.

The main challenges will be making the agents work together, and working with
uncertainty.

Initially Mr. X. will be contolled by a human user, but if time allows it we
could also make an AI for that.

\section{Implementation} % {{{
\label{sec:imp}
The world will consist of an array of nodes.
A node will be a class that contains an \texttt{IdentityHashTable} of connections to
other nodes, and 4 \texttt{Linkedlists} for each type of connection that refer to
neighbouring nodes. The former is quick for random access ($O(1)$), and the
latter have minimal complexity for iteration of specific connection types, and
minimal memory footprint; both in $O(n)$.

AI techniques that will be used are $A^*$ for path-planning. Heuristics can be
used to represent the scarceness of different types of cards. Value functions can
be constructed for different nodes that take into account the probability that Mr. X.
is on or near that node, the distance to other detectives, and the amount of
nodes that can be cut from the possible positions of Mr. X.

We will make a model for predicting the most likely actions for Mr. X.
% section imp }}}

\end{document}
